package com.yufang.Day09_29;

/**
 * 35
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 你可以假设数组中无重复元素。
 * 示例 1:
 * 输入: [1,3,5,6], 5
 * 输出: 2
 * 示例 2:
 * 输入: [1,3,5,6], 2
 * 输出: 1
 */
public class D_1 {

    public static void main(String[] args) {
        int[] nums = new int[9];
        nums[0] = 2;
        nums[1] = 3;
        nums[2] = 4;
        nums[3] = 5;
        nums[4] = 7;
        nums[5] = 8;
        nums[6] = 9;
        nums[7] = 10;
        nums[8] = 11;
        int index = getAns(nums,6);
        System.out.println(index);
    }

    private static int getAns(int[] nums, int target) {

        int left = 0;
        int right = nums.length-1;
        if(target > nums[right]) return nums.length;
        else if(target <= nums[0]) return 0;
        return ef(nums,left,right,target);

    }

    private static int ef(int[] nums, int left, int right,int target) {

        //二分查找
        int min = (left+right+1) / 2;
        if(target > nums[min]){
            if(target < nums[min+1]) return min+1;
            return ef(nums,min,right,target);
        }else if(target < nums[min]){
            if(target > nums[min-1]) return min;
            return ef(nums,left,min,target);
        }else {
            return min;
        }

    }

}
